package com.cn.algorithm02.class14;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description: 寻找最小祖宗
 * 给一个头节点head（可能是子树的头节点，因此ab不一定汇聚）， 两个节点a，b，求ab的最小公共祖先节点
 **/
public class C03_LowestAncestor {
    public static void main(String[] args) {
        int[] arr = {1, 4, 20, 1, 6, 17, 22};
        Nodea head = Nodea.getNodeInstance(arr);
        head.left.right.right = new Nodea(8);

        Nodea.printTree(head);
        Nodea a = head.left.right;
        Nodea b = head.left.right.right;
        System.out.println(lowestAncestor(null, a, b));
    }

    public static Nodea lowestAncestor(Nodea head, Nodea a, Nodea b) {
        return process(head, a, b).ans;
    }

    public static Info process(Nodea x, Nodea a, Nodea b) {
        if (x == null) return new Info(false, false, null);

        Info leftInfo = process(x.left, a, b);
        Info rightInfo = process(x.right, a, b);
        boolean findA = x == a || leftInfo.findA || rightInfo.findA ? true : false;
        boolean findB = x == b || rightInfo.findB || rightInfo.findB ? true : false;


        Nodea ans = null;
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        } else if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        } else if (findA && findB) {
            ans = x;
        }
        return new Info(findA, findB, ans);
    }

    public static class Info {
        public boolean findA;
        public boolean findB;
        public Nodea ans;

        public Info(boolean findA, boolean findB, Nodea ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

}
